// 2025/10/26
// 环形子数组的最大和

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int ans = nums[0], n = nums.size();
        vector<int> leftMax(n);
        leftMax[0] = nums[0];
        // 第一种情况
        int prev = nums[0], leftSum = nums[0];
        for(int i = 1; i < n; i++)
        {
            prev = max(prev + nums[i], nums[i]);
            ans = max(ans, prev);
            leftSum += nums[i];
            leftMax[i] = max(leftMax[i - 1], leftSum);
        }

        // 第二种情况
        int rightSum = 0;
        for(int i = n - 1; i > 0; i--)
        {
            rightSum += nums[i];
            ans = max(ans, rightSum + leftMax[i - 1]);
        }
        return ans;
    }
};